package com.zlk.algorithm.algorithm.dynamicPlan.arraySum;

// 子数组最大累加和
// 给你一个整数数组 nums
// 返回非空子数组的最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-subarray/
public class Code01_MaximumSubarray {

    /**
     * 代表以第 i 个数结尾的「连续子数组的最大和」
     *   dp[i]  dp[i-1]>0依赖前面位置
     *          dp[i-1]<=0 不依赖前面位置
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        return f(nums);
    }

    private int  f(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i-1]>0){
                dp[i] = dp[i-1]+nums[i];
            }else{
                dp[i] = nums[i];
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }


    private int  f2(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int ans = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i-1]>0){
                dp[i] = dp[i-1]+nums[i];
            }else{
                dp[i] = nums[i];
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }

    private int  f3(int[] nums) {
        //int[] dp = new int[nums.length];
        int pre =nums[0];
        int ans = pre;
        for (int i = 1; i < nums.length; i++) {
            if(pre>0){
                pre = pre+nums[i];
            }else{
                pre = nums[i];
            }
            ans = Math.max(ans,pre);
        }
        return ans;
    }

    // 如下代码为附加问题的实现
    // 子数组中找到拥有最大累加和的子数组
    // 并返回如下三个信息:
    // 1) 最大累加和子数组的开头left
    // 2) 最大累加和子数组的结尾right
    // 3) 最大累加和子数组的累加和sum
    // 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
    private int  f4(int[] nums) {
        //int[] dp = new int[nums.length];
        int pre =nums[0];
        int left =0;
        int right =0;
        int sum = pre;
        int ans = pre;
        for (int i = 1; i < nums.length; i++) {
            if(pre>0){
                right = i;
                sum = sum+nums[i];
                pre = pre+nums[i];
            }else{
                left = i;
                right = i;
                sum = nums[i];
                pre = nums[i];
            }
            ans = Math.max(ans,pre);
        }
        return ans;
    }


}
